package likou.tanxin;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/17 06:53
 */
public class _1005 {
    public static void main(String[] args) {
        System.out.println(largestSumAfterKNegations(new int[]{4,2,3},1));
    }
    public static int largestSumAfterKNegations(int[] A, int K) {
        quickSort(A,0,A.length-1);
        int index = 0;
        while(K!=0){
            boolean p = false;
            while(K!=0&&index<A.length&&A[index]<0){
                A[index] = - A[index];
                K--;
                index++;
                p = true;
            }
            if(A[index]==0||K==0){
                break;
            }
            if(p){
                quickSort(A,0,A.length-1);
            }
            A[0] = K%2==0?A[0]:-A[0];
            K=0;
        }
        int daan = 0;
        for(int i:A){
            daan+=i;
        }
        return daan;
    }
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        //递归结束条件：startIndex大于或等于endIndex时
        if (startIndex >= endIndex) {
            return;
        }
        //得到基准元素位置
        int pivotIndex = partition(arr, startIndex, endIndex);
        //根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }
    /**
     * 快速排序法 递归 分治（双边循环法）
     *
     * @param arr
     * @param startIndex
     * @param endIndex
     * @return
     */
    private static int partition(int[] arr, int startIndex, int endIndex) {
        //去第一个位置（也可以选择随机位置）的元素作为基准元素
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            //控制right指针比较，并左移
            while (left < right && arr[right] > pivot) {
                right--;
            }
            //交换left指针比较，并右移
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //交换left和right指针所指向的元素
            if (left < right) {
                int p = arr[left];
                arr[left] = arr[right];
                arr[right] = p;
            }
        }
        //pivot和指针重合点交换
        arr[startIndex] = arr[left];
        arr[left] = pivot;

        return left;
    }
}
